package practice1_100;

import java.util.HashMap;
import java.util.Map;

public class Practice264 {
    static Map<Integer,Boolean> map=new HashMap<>();
    public int nthUglyNumber(int n) {
        int temp=0;
        for (int i = 1; i <= Integer.MAX_VALUE&&n>0; i++) {
            if(isUgly(i)) {
                temp=i;
                n--;
            }
        }
        return temp;
    }
    public boolean isUgly(int n) {
        if(n==0) return false;
        //弄一个dp表
//        Map<Integer,Boolean> map=new HashMap<>();
        return dp(map,n);
    }

    public boolean dp(Map<Integer,Boolean> map,int n){
        boolean a = false,b = false,c=false;
        if(n==2||n==3||n==5||n==1) {
            map.put(n,true);
            return map.get(n);
        }

        if(n%2==0)  {
            if(map.get(n/2)!=null&&map.get(n/2)==true) a=true;
            else {
                map.put(n/2,dp(map,n/2)) ;
                a=map.get(n/2);
            }
        }
        if(n%3==0) {
            if(map.get(n/3)!=null&&map.get(n/3)==true) b=true;
            else {
                map.put(n/3,dp(map,n/3)) ;
                b=map.get(n/3);
            }
        }
        if(n%5==0) {
            if(map.get(n/5)!=null&&map.get(n/5)==true)  b=true;
            else {
                map.put(n/5,dp(map,n/5)) ;
                b=map.get(n/5);
            }
        }

        return a||b||c;
    }

    public static void main(String[] args) {
       int a= new Practice264().nthUglyNumber(2000);
        System.out.println(a);
    }
}
